Greedy vs Brute Force
👩🏫 Secara Formal:
Dalam memecahkan masalah komputasi (khususnya OSN), kita harus memilih strategi yang tepat antara mencari kepastian absolut atau mencari kecepatan.
- Brute Force (Pencarian Lengkap): Mencoba SETIAP KEMUNGKINAN solusi satu per satu sampai ketemu yang benar. Keunggulan: Pasti menemukan jawaban (100% akurat). Kelemahan: Sangat lambat jika datanya besar (Bisa *Time Limit Exceeded* / TLE).
- Greedy (Rakus/Tamak): Mengambil keputusan lokal terbaik pada saat itu juga, tanpa memikirkan konsekuensi ke depan. Keunggulan: Sangat cepat. Kelemahan: Tidak selalu menghasilkan solusi global yang optimal.
Analogi Jaman Now
Brute Force
Kamu lupa pin koper 3 digit. Kamu coba dari 000, 001, 002... terus sampai 999. Pasti bakal kebuka kopernya! Tapi bayangin kalau jarimu keriting gara-gara nyoba 1000 kali.
Greedy
Kamu kasir minimarket mau ngasih kembalian Rp 17.000. Kamu rakus langsung ambil pecahan terbesar (10rb), sisanya (7rb) ambil pecahan terbesar lagi (5rb), lalu (2rb). Beres! Cepat tanpa mikir panjang.
Simulasi Algoritma Greedy (Coin Change)
Masukkan jumlah kembalian. Komputer (Greedy) akan mencoba menukar dengan jumlah koin/uang paling sedikit dengan selalu memprioritaskan pecahan terbesar terlebih dahulu.
⚠️ Common Mistakes: Jebakan Greedy (Greedy Fails)
Siswa OSN sering tertipu dan menganggap Greedy selalu memberikan solusi terbaik (optimal). Ini SALAH BESAR! Greedy Coin Change hanya berfungsi optimal pada pecahan uang normal (seperti Rupiah: 100, 50, 20).
Coba bayangkan pecahan koinnya adalah [4, 3, 1] dan target 6.
- Greedy: 4 + 1 + 1 (Butuh 3 koin).
- Solusi Optimal (DP): 3 + 3 (Hanya butuh 2 koin!).
Jangan gunakan Greedy jika soal tidak terbukti *Greedy Choice Property*-nya (Gunakan Dynamic Programming!).
Brute Force Password Cracker
Simulasi pencarian lengkap. Sistem akan mencoba semua kemungkinan angka 3 digit (000 - 999) sampai cocok dengan password rahasia yang kamu buat.
⚠️ Common Mistakes: Time Limit Exceeded (TLE) & Kurangnya Pruning
Pada soal kompetitif, sistem otomatis seperti TLX / HackerRank akan memberikan batas waktu (biasanya 1 detik). Algoritma Brute Force murni pada data besar ($N > 10.000$) hampir dipastikan terkena TLE (Time Limit Exceeded). Kesalahan umum lainnya adalah lupa melakukan Pruning (Pemangkasan), yaitu tidak menghentikan pencarian/looping dengan `break;` setelah jawaban sudah ditemukan, membiarkan program terus mencoba sisa kombinasi yang sia-sia.